The Discrete Fourier Transform (DFT) is a linear transformation that maps a sequence of N input numbers x_0 to x_N−1 (input operands) into a corresponding set of N transformed numbers X_0 to X_N−1 (output operands). The output operands are also known as the spectrum of the input operands. A Fast Fourier Transform (FFT) is a processing scheme for carrying out a DFT numerically in an efficient manner. A DFT is representable as a non-sparse N-by-N matrix. The Cooley-Tukey algorithm is probably the most widely-used FFT algorithm. It exploits the fact that the DFT can be represented as a product of sparse N-by-N matrices. It transforms the input operands in a sequence of several rounds. Each round is a linear transformation between a set of input operands and a corresponding set of output operands. The output operands of a given round are used as the input operands of the next round until the final output operands, i.e., the DFT of the initial input operands, are obtained. Each of these linear transformations may be represented by a sparse matrix and therefore can be carried out rapidly.
Each round of the FFT may involve the evaluation of radices of order P, commonly referred to as radix-P butterflies or simply as butterflies. A radix P butterfly is a linear transformation between P input operands and P output operands. In many implementations, the radix order P is two, four, or eight. In each round, the N input operands may be partitioned into N/P sets of input operands. Each of these sets may be transformed individually, i.e., independently of the other sets of input operands, by means of the radix P butterfly.
The input operands x_1 to x_N may, for example, be the values of a continuous function x(t) defined on a certain finite interval [t_a, t_b]. In this case, the output operands of the FFT may be considered approximate values of the N leading Fourier coefficients of the function x(t), i.e., the leading N coefficients of an expansion of x(t) onto a discrete orthonormal basis set of complex plane waves. The basis functions, i.e., the complex plane waves, satisfy periodic boundary conditions. It can therefore be beneficial to apply a window function to the input operands prior to the first round of the FFT so as to reduce the amplitude of one or more successive input operands prior to performing the FFT. In this context, the input operand x_0 may be considered the successor to the input operand x_N−1, in accordance with the periodic boundary conditions. The modified input operands thus obtained may be referred to as the weighted or windowed input operands xw_0 to xw_N−1. In a simple example, xw_0=0, xw_I=x_I for I=1 to N−2, and x_N−1=0. Applying the FFT to the windowed input operands instead of the original input operands may reduce the effect known as leakage in FFT processing and produce a spectrum that can be more suitable for further analysis or processing.
In a decimation-in-time (DIT) FFT, the butterflies of a given round are pre-multiplied by a set of interstage twiddle coefficients. In a decimation-in-frequency (DIF) FFT, the butterflies of a given round are post-multiplied by a set of interstage twiddle coefficients.